package day2;

import java.util.Scanner;

//思想： 模拟+贪心

//时间复杂度：O(n)
public class 数组中两字符串的最小距离 {
	
	//思路：
	//   1.prev1记录字符串s1在[0,i)的最大下标，prev2记录字符串s2在[0,i)的最大下标
	//   2.遍历数组，到i位置时且str[i]为s1或者s2时，从[0,i)中找相反字符串的最大下标，更新结果
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            String s1=in.next();
            String s2=in.next();
            String[] str=new String[n];

            for(int i=0;i<n;i++){
                str[i]=in.next();
            }
            //prev1: 记录字符串s1在区间[0,i)的最大下标
            //prev2: 记录字符串s2在区间[0,i)的最大下标
            int prev1=-1,prev2=-1;
            int ret=n+1;
            for(int i=0;i<n;i++){
            	//如果字符串str[i]为s1
                if(s1.equals(str[i])){
                    if(prev2!=-1){
                        ret=Math.min(ret,i-prev2);
                    }
                    //更新位置
                    prev1=i;
                }
              //如果字符串str[i]为s2
                else if(s2.equals(str[i])){
                    if(prev1!=-1){
                        ret=Math.min(ret,i-prev1);
                    }
                    //更新位置
                    prev2=i;
                }
            }
            if(prev1==-1||prev2==-1){
                System.out.println(-1);
            }
            else{
                System.out.println(ret);
            }
        }
	}
	
	public static void main1(String[] args) {
		Scanner in = new Scanner(System.in);
		// 注意 hasNext 和 hasNextLine 的区别
		
		//我的想法：
		// 总： 定义两个变量p1,p2，用p2遍历整个数组，p1保存的是与p2相反的字符串的最近下标
		//     如果p2遇到s1,则如果p1指向的是s2,就更新距离，否则不更新，之后同理
		//     每次只要遇到s1或者s2就更新p1的值，这是为了构成最小的距离
		while (in.hasNext()) { // 注意 while 处理多个 case
			int n = in.nextInt();
			String str1 = in.next();
			String str2 = in.next();
			String[] strs = new String[n];
			for (int i = 0; i < n; i++) {
				strs[i] = in.next();
			}
			if (str1 == null || str2 == null) {
				System.out.println(-1);
			} 
			else {
				int p1 = -1, p2 = 0;
				int ret = n+1;
				while (p2 < n) {
					if (strs[p2].equals(str1) == true) {
						if(p1>=0&&strs[p1].equals(str2)==true){
							ret = Math.min(ret, p2 - p1);
						}
						p1=p2;
					}
					else if (strs[p2].equals(str2) == true) {
						if(p1>=0&&strs[p1].equals(str1)==true) {
							ret = Math.min(ret, p2 - p1);
						}
						p1=p2;
					}
					p2++;
				}
				ret=ret==n+1?-1:ret;
				System.out.println(ret);
			}
		}
	}

}
